package com.platform.modules.alg.alglib.poj1190;

public class Poj1190 {
    private final int N = 30;
    private final int inf = 0x3f3f3f3f;
    private int n;
    private int m;
    private int minv[] = new int[N];
    private int mins[] = new int[N];
    private int best;

    public String output = "";

    void init() {
        minv[0] = mins[0] = 0;
        for (int i = 1; i < 22; i++) {
            minv[i] = minv[i - 1] + i * i * i;
            mins[i] = mins[i - 1] + 2 * i * i;
        }
    }

    void dfs(int dep, int sumv, int sums, int r, int h) {
        if (dep == 0) {
            if (sumv == n && sums < best) best = sums;
            return;
        }
        if (sumv + minv[dep] > n || sums + mins[dep] > best || sums + 2 * (n - sumv) / r > best) return;
        for (int i = r; i >= dep; i--) {
            if (dep == m) sums = i * i;
            int maxh = Math.min((n - sumv - minv[dep - 1]) / (i * i), h);
            for (int j = maxh; j >= dep; j--)
                dfs(dep - 1, sumv + i * i * j, sums + 2 * i * j, i - 1, j - 1);
        }
    }

    public String cal(String input) {
        init();
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        best = inf;
        dfs(m, 0, 0, n, n);
        if (best == inf) {
            output = "0";
        } else {
            output = String.valueOf(best);
        }

        return output;
    }
}
